5번문제 역시 난이도가 중입니다. 이번 문제에서 조금 주의해야 할 점은 집합에 중복된 원소가 들어가는 것을 허용하는 것입니다. STL 등에서 제공하는 라이브러리 중 multiset, multimap 등 중복을 허용하는 자료구조가 있지만, 사실 저런 원소를 사용할 필요 없이 일반적인 hash, map 등으로 풀 수 있습니다.
원리는 간단합니다. substring 과 int를 가지는 map을 선언하여, 해당 원소의 개수만큼 count를 해줍니다. 그 다음 교집합을 구할 때는 두 집합중 더 적은 갯수의 원소를 가진 쪽의 갯수, 합집합일 때는 더 많은 갯수의 원소를 가진 쪽의 갯수를 취하면 됩니다. 즉
$A=\{1,1,2,2,3\}$ 이고 $B=\{2,3,3,4\}$ 라면, $A[1]=2, B[1]=0, A[2]=2, B[2]=1, A[3]=1, B[3]=2, B[4]=1$ 로 처리를 할 수 있고, 둘중 더 많은쪽과 적은쪽을 각각 교집합과 합집합에 더해주면 됩니다.
문제에서 예외로 발생하는 경우는 공집합일 경우 이를 유사도 1로 규정하라고 되어 있는데, 사실 문제의 정의대로라면 A+B, C*D 도 유사도가 1이 되어버리는 조금 이상한 가정을 하고 있는 것을 알 수 있습니다. 왜 이렇게 했는지는 모르겠지만.. 최종적으로 계산 전 0으로 나뉘는 것을 막기 위해 전처리를 해주면 됩니다.
마지막으로, 문제를 편하게 풀기 위해 모든 문자열을 대문자로 바꾸고 시작합니다.(소문자로 바꿔도 아무상관 없음) 그리고 map의 특성상 존재하지 않는 key를 비교하려고 할 경우 데이터를 집어넣게 되어 비교만으로 불필요한 연산이 늘어날 수 있는 문제가 있습니다. 따라서 밑의 소스에서는 count를 이용해 존재 여부를 체크한 다음 비교하여 불필요한 연산을 최소화 하였습니다.
int solve(string str1, string str2)
{
transform(str1.begin(), str1.end(), str1.begin(), ::toupper);
transform(str2.begin(), str2.end(), str2.begin(), ::toupper);
int a = 0, b = 0;
map<string, int> mp1, mp2;
for (int i = 0; i < str1.length() - 1; i++)
{
string substr1 = str1.substr(i, 2);
if ('A' <= substr1[0] && substr1[0] <= 'Z'&&'A' <= substr1[1] && substr1[1] <= 'Z')
{
mp1[substr1]++;
}
}
for (int i = 0; i < str2.length() - 1; i++)
{
string substr2 = str2.substr(i, 2);
if ('A' <= substr2[0] && substr2[0] <= 'Z'&&'A' <= substr2[1] && substr2[1] <= 'Z')
{
mp2[substr2]++;
}
}
for (auto it : mp1)
{
if (mp2.count(it.first) > 0)
{
a += min(it.second, mp2[it.first]);
b += max(it.second, mp2[it.first]);
}
else
{
b += it.second;
}
}
for (auto it : mp2)
{
if (mp1.count(it.first) == 0)
{
b += it.second;
}
}
if (!a) a = 1;
a *= 65536;
if (!b) b = 1;
return a / b;
}